/*
 * tdeapporo.cpp
 *
 *  Created on: 28/04/2010
 *      Author: javier
 */
#include <iostream>
#include "tdeapporo.h"
#include <math.h>

using namespace std;

TDeapPoro::TDeapPoro()
:v(10),posicion(2)
 {}


TDeapPoro::TDeapPoro( const TDeapPoro &deap)
{
	v =  deap.v;
	posicion = deap.posicion;
}

TDeapPoro::~TDeapPoro()
{
	posicion = 0;
}

TDeapPoro &
TDeapPoro::operator =( const TDeapPoro &deap)
{
	if( this != &deap )
	{
		if ( posicion != 0 )
		{
			v = deap.v;
			posicion = deap.posicion;
		}
		else
		{
			this->~TDeapPoro();
			v = deap.v;
			posicion = deap.posicion;
		}
	}
	return *this;
}

bool
TDeapPoro::operator ==( const TDeapPoro &deap)
{
	bool igual = false;

	if( v == deap.v ) igual = true;

	return igual;
}

bool
TDeapPoro::EsVacio() const
{
	bool vacio = false;

	if( posicion <=2 ) vacio = true;//cuando esta vacio vale 2

	return vacio;
}

bool
TDeapPoro::Insertar(const TPoro &p)
{
	bool insertado = false;
	THeap heap;
	int j = 0, i = 0;

	//Como en una lista, comprobamos si esta vacia, si esta el elemento etc.

	if( posicion == 2 )
	{
		v[posicion] = p;
		posicion++;
		insertado = true;

	}
	else
	{
		//Tendriamos que comprobar si esta el elemento en el resto del vector.
		if( !this->Buscaporo(p) )// Si no esta en el vector.
		{
			//Insertamos. Comprobar el tamaño del vector por si esta lleno.
			if( posicion > v.Longitud() ) v.Redimensionar(v.Longitud()+10);

			v[posicion] = p; // Insertamos redimensione o no.
			//Comparamos el nodo con el simétrico como pone en los apuntes.
			//Para ello primero tenemos que saber en que Heap esta.

			heap = IdentificaHeap(posicion);



			if ( heap == Hmin )
			{
				i = posicion;
				j = SimetricoMaximo(posicion);


				if( v[posicion].Volumen() > v[j].Volumen() )
				{

					Intercambiar(i,j);

					heap = Hmax;

				}

				insertado = true;
			}
			else
			{
				j = posicion;
				i = this->SimetricoMinimo(posicion);

				if( v[posicion].Volumen() < v[i].Volumen() ) // Si el q esta en el mayor es + pek...
				{

					Intercambiar(j,i);

					heap = Hmin;

				}
				//this->AscensionMax(posicion);
				insertado = true;
			}

			if( heap == Hmin )
			{
				AscensionMin(i);
			}
			else
			{
				AscensionMax(j);
			}
			posicion++; //Iteramos la proxima posicion libre.

		}
	}
	return insertado;
}

bool
TDeapPoro::Buscaporo(const TPoro &p)
{
	bool iguales = false;

	for( int i = 2; i < v.Longitud(); i++)
	{
		if( v[i].Volumen() == p.Volumen() )
		{
			iguales = true;
			i = v.Longitud(); // saldra del bucle
		}
	}

	return iguales;
}

THeap
TDeapPoro::IdentificaHeap(const int p) const
{
	int pos = 0;
	pos = p;
	THeap heap;

	if( p == 2 ) heap = Hmin;
	else if( p == 3 ) heap = Hmax;
	else
	{
		do
		{
			pos = pos / 2;

		}while( pos > 2 );

		if( pos == 2 ) heap = Hmin;
		else if ( pos == 3 ) heap = Hmax;
	}

	return heap;
}

int
TDeapPoro::SimetricoMaximo( const int i) const
{
	int j = 0;

	j = i + pow( 2.0, (int)(log2(i)-1));

	if( j > posicion ) j = j/2;

	return j;
}

int
TDeapPoro::SimetricoMinimo( const int j) const
{
	int i = 0;

	if( j == 3 )
		i = 2;
	else
		i = j - pow( 2, (int)(log2(j)-1));

	return i;
}

void
TDeapPoro::Intercambiar(int i, int j)
{
	TPoro aux;
	aux = v[i];
	v[i] = v[j];
	v[j] = aux;
}

void
TDeapPoro::AscensionMin( int i)
{

    while( i>2 && (v[i].Volumen() < v[i/2].Volumen() ) )
    {
        Intercambiar(i,i/2);
        i=i/2;
    }


}

void
TDeapPoro::AscensionMax( int j)
{
	 while( j>3 && (v[j].Volumen() > v[j/2].Volumen()))
	     {
	         Intercambiar(j,j/2);
	         j=j/2;
	     }
}

bool
TDeapPoro::BorrarMax()
{
	bool borrado = false;
	//THeap heap;
	int j = 3, i = 0; // j para recorrer el heap empieza en 3 por el elemento maximo, i para el simetrico mas adelante


	if( posicion > 2 )
	{
		if( v.Cantidad()+10 < v.Longitud())
		{
			TVectorPoro vaux(v.Longitud()-10);
			for( int k = 0; k < vaux.dimension; k++ )
			{
				vaux[k] = v[k];
			}
			v = vaux;

		}

		//Intercambiar elemento para borrar, primer paso en apuntes.
		posicion--;
		v[3] = v[posicion];

		//hundir el elemento

		while( (j*2 < posicion) || (j*2+1 < posicion) ) // Condicion de salida
		{
			if( j*2 < posicion )
			{
				if( v[j*2].Volumen() > v[j*2+1].Volumen() )
				{
					this->Intercambiar(j, j*2); //Hijo izquierda formula i*2
					j = j*2;
				}
				else
				{
					this->Intercambiar( j, j*2+1 ); // Hijo derecha formula i*2+1
					j = j*2+1;
				}
			}
			else
			{
				//this->Intercambiar( j, j*2 );
				j = j*2;
			}
		}

		borrado = true;
		//Comprobar que no incumpla el Deap con el simétrico
		i = this->SimetricoMinimo(j);
		if( v[i].Volumen() > v[j].Volumen() )
		{
			this->Intercambiar(i,j);
			this->AscensionMin(i);
			this->AscensionMax(j);
		}

		if((i*2 < posicion) && (i*2+1 < posicion) )
		{
			if( v[i*2].Volumen() > v[i*2+1].Volumen() )
			{
				i=i*2;
				if( v[i].Volumen() > v[j].Volumen() )
				{
					this->Intercambiar(i,j);
					this->AscensionMin(i);
					this->AscensionMax(j);
				}
			}
			else
			{
				i=i*2+1;
				if( v[i].Volumen() > v[j].Volumen() )
				{
					this->Intercambiar(i,j);
					this->AscensionMin(i);
					this->AscensionMax(j);
				}
			}
		}
		else if(i*2 < posicion)
		{
			i=i*2;
			if( v[i].Volumen() > v[j].Volumen() )
			{
				this->Intercambiar(i,j);
				this->AscensionMin(i);
				this->AscensionMax(j);
			}
		}
	}

	return borrado;
}

bool
TDeapPoro::BorrarMin()
{
	bool borrado = false;
//	THeap heap;
	int j = 2, i = 0; // "j" para recorrer el heap, "i" para indicar el simetrico mas adelante

	if( posicion > 2 )
	{
		if( v.Cantidad()+10 < v.Longitud())
		{
			TVectorPoro vaux(v.Longitud()-10);
			for( int k = 0; k < vaux.dimension; k++ )
			{
				vaux[k] = v[k];
			}
			v = vaux;

		}

		//Intercambiar elemento para borrar, primer paso en apuntes.
		posicion--;
		v[2] = v[posicion];

		//hundir el elemento

		while( (j*2 < posicion) || (j*2+1 < posicion) )
		{
			if( j*2 < posicion )
			{
				if( v[j*2].Volumen() < v[j*2+1].Volumen() )
				{
					this->Intercambiar(j, j*2); //Hijo izquierda formula i*2
					j = j*2;
				}
				else
				{
					this->Intercambiar( j, j*2+1 ); // Hijo derecha formula i*2+1
					j = j*2+1;
				}
			}
			else
			{
				this->Intercambiar( j, j*2 );
				j = j*2;
			}

			borrado = true;
			//Comprobar que no incumpla el Deap con el simétrico
			i = this->SimetricoMaximo(j);

			if( v[i].Volumen() < v[j].Volumen() )
			{
				this->Intercambiar(i,j);
				this->AscensionMax(i);
				this->AscensionMin(j);
			}
		}
		int aux = 0; //Comprueba si el DEAP cumple la condicion 4.
		for( int k = 2; k < posicion; k++ )
		{
			if( IdentificaHeap(k) == Hmin )
			{
				aux = SimetricoMaximo(k);

				if( v[k].Volumen() > v[aux].Volumen() )
				{
					Intercambiar(k,aux);
					this->AscensionMax(aux);
				}
			}
		}



	}

	return borrado;
}

TPoro
TDeapPoro::Max() const
{
	TPoro a;
	if ( posicion > 3  )
	{
		a = v[3]; // Tercera posicion elemento maximo
	}
	else if( posicion > 2)
	{
		a = v[2];
	}

	return a;
}


TPoro
TDeapPoro::Min() const
{
	TPoro a;
	if ( !this->EsVacio()  ) a = v[2]; //segunda posicion elemento minimo

	return a;
}

int
TDeapPoro::Altura() const
{
	int auxpos = posicion, nivel = 0; // Mirar esto!
	auxpos--;

	if(auxpos==1)
	{
			nivel=0;
	}
	else
	{
		while( auxpos >= 1)
		{
			auxpos = auxpos/2;
			nivel++;
		}
	}
	return nivel;
}

int
TDeapPoro::Nodos() const
{
	int aux = posicion;
	aux--;
	if(aux==1)
		aux=0;
	return aux;
}

TVectorPoro
TDeapPoro::Inorden() const
{
	int i = 1, p = 1; // Para que salgan los calculos contamos i desde 1.

	TVectorPoro vin(posicion-1);

	this->InordenAux(vin, i, p);

	return vin;
}

TVectorPoro
TDeapPoro::InordenAux( TVectorPoro &vin, int i, int &auxposicion) const
{
	if( i < posicion )
	{
		InordenAux( vin, i*2, auxposicion);
		vin[auxposicion] = v[i];
		auxposicion++;
		InordenAux( vin, (i*2)+1, auxposicion);
	}

	return vin;
}


TVectorPoro
TDeapPoro::Preorden() const
{
	int i = 1, p = 1; // Para que salgan los calculos contamos desde 1

	TVectorPoro vin(posicion-1);

	this->PreordenAux(vin, i, p);

	return vin;
}

TVectorPoro
TDeapPoro::PreordenAux( TVectorPoro &vin, int i, int &auxposicion) const
{
	if( i < posicion )
	{
		vin[auxposicion] = v[i];
		auxposicion++;
		PreordenAux( vin, i*2, auxposicion);
		PreordenAux( vin, (i*2)+1, auxposicion);
	}

	return vin;
}

TVectorPoro
TDeapPoro::Postorden() const
{
	int i = 1, p = 1; // Para que salgan los calculos contamos desde 1

	TVectorPoro vin(posicion-1);

	this->PostordenAux(vin, i, p);

	return vin;
}

TVectorPoro
TDeapPoro::PostordenAux( TVectorPoro &vin, int i, int &auxposicion ) const
{
	if( i < posicion )
	{
		PostordenAux( vin, i*2, auxposicion);
		PostordenAux( vin, (i*2)+1, auxposicion);
		vin[auxposicion] = v[i];
		auxposicion++;
	}

	return vin;
}

TVectorPoro
TDeapPoro::Niveles() const
{
	TVectorPoro vaux(posicion-1);

	for(int i = 2; i < posicion; i++)
	{
		vaux[i] = v[i];
	}

	return vaux;
}

ostream &
operator<<( ostream &os, const TDeapPoro &deap )
{
	os << deap.Niveles();

	return os;
}
